package 力扣链表;

public class 面试题0204分割链表 {
    //
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode smailHead = new ListNode();
        ListNode smailTail = smailHead;
        ListNode bigHead = new ListNode();
        ListNode bigTail = bigHead;

        while (head != null){
            if (head.val < x){
                smailTail.next = head;
                smailTail = head;
            }else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        bigHead.next = null;
        smailTail.next = bigHead.next;
        return smailHead.next;
    }
}
